package com.leetcode.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LongestIncrArray {
    public int[] lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return new int[0];
        }
        // 贪心算法+二分查找
        // 贪心：总是记录定长序列的末尾的最小值，二分：更新最小值的方式是二分查找获取索引
        // tail 数组的定义：长度为 i + 1 的上升子序列的末尾最小是几
        int[] tail = new int[len];
        int[] path = new int[len];
        tail[0] = nums[0];
        path[0] = 0;
        int end = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i] > tail[end]) {
                end++;
                tail[end] = nums[i];
                path[end] = i;
            } else {
                int left = 0, right = end;
                while (left < right) {
                    int mid = (left + right) / 2;
                    if (tail[mid] < nums[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tail[left] = nums[i];
                path[left] = i;
            }
        }
        return Arrays.copyOfRange(path, 0, end + 1);
    }

    public static void main(String[] args) {
        // int[] nums = new int[] { 10, 9, 2, 5, 3, 7, 101, 18 };
        int[] nums = new int[] { 0, 1, 0, 3, 2, 3 };
        int[] res = new LongestIncrArray().lengthOfLIS(nums);
        List<Integer> resList = new ArrayList<Integer>();
        for (int index : res) {
            resList.add(nums[index]);
        }
        System.out.println(resList);
    }
    
}
